package com.it.od.old2021.od;

/**
 * @author: liminghui
 * @date: 2022/8/1 0:18
 * @version: 1.0
 * @description: 翻转链表
 */
public class Main2 {
    public static void main(String[] args) {

    }

    // 区间链表翻转
    public static ListNode reverseBetween(ListNode head, int m, int n) {
        // 构造头节点
        ListNode listNode = new ListNode(-1);
        listNode.next = head;
        ListNode start = listNode;
        // 找到m节点 循环m-1次 start指向m-1
        for (int i = 0; i < m - 1; i++) {
            start = start.next;
        }
        ListNode log = start;
        ListNode end = start;
        for (int i = m; i < n; i++) {
            end = end.next;
        }
        // 获得m到n节点之间的链
        ListNode node = start.next;
        ListNode cur = end.next;
        // 断开
        start.next = null;
        end.next = null;
        ListNode listNode1 = reverseList(node);

        // 拼接
        log.next = listNode1;
        ListNode sd = listNode1;
        while (sd.next != null) {
            sd = sd.next;
        }
        sd.next = cur;
        return listNode.next;
    }

    // 翻转链表
    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;  // 后移
            cur = tmp; // 后移
        }
        return pre;
    }

    public static class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
}
